package com.zyk.grate_offer.class03;

import java.util.Arrays;

/**
 * 力扣： https://leetcode-cn.com/problems/closest-subsequence-sum/
 *
 * @author zhangsan
 * @date 2021/4/28 13:06
 */
public class Code06_ClosestSubSequenceSum {

    // 分治， 数组长度不大， 数据很大， 如果做动态规划表会爆掉
    public static int minAbsDifference(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int N = nums.length;
//        int[] l = new int[1 << 20];    // 左边所有累加和
//        int[] r = new int[1 << 20];
        int[] l = new int[1 << ((N + 1) / 2)];    // 左边所有累加和
        int[] r = new int[1 << ((N + 1) / 2)];
        int le = process(nums, 0, N >> 1, 0, 0, l);
        int re = process(nums, N >> 1, N, 0, 0, r);
        Arrays.sort(l, 0, le);
        Arrays.sort(r, 0, re);
        int ans = Math.abs(goal);
        for (int i = 0; i < le; i++) {      // 左边和右边来个匹配， 都是升序， 所以从左边开始， 右边结束双指针搞
            int rest = goal - l[i];
            while (re > 0 && Math.abs(rest - r[re - 1]) <= Math.abs(rest - r[re])) {
                re--;
            }
            ans = Math.min(ans, Math.abs(rest - r[re]));
        }
        return ans;
    }

    /**
     * 填充累加和
     *
     * @param nums 原数组
     * @param i    当前下标
     * @param end  结束的位置
     * @param fill 填充数组的下标
     * @param sum  当前累加和
     * @param arr  填充的数组
     * @return 填充这个后的下标
     */
    public static int process(int[] nums, int i, int end, int fill, int sum, int[] arr) {
        if (i == end) {
            arr[fill++] = sum;
        } else {
            fill = process(nums, i + 1, end, fill, sum, arr);   // 不要这个数
            fill = process(nums, i + 1, end, fill, sum + nums[i], arr);   // 要这个数
        }
        return fill;
    }

    // for test
    public static void main(String[] args) {
//        int[] nums = new int[40];     //2097152
        int[] nums = new int[30];       // 1073741824
        System.out.println("数组全排列个数： " + (1 << nums.length) );
    }

}
